package com.zjsru.leetcode75.level1;

/**
 * @Author: cookLee
 * @Date: 2023-11-26
 * 寻找峰值
 */
public class FindPeakElement {

    /**
     * 主
     * \
     * 输入：nums = [1,2,3,1]
     * 输出：2
     * 解释：3 是峰值元素，你的函数应该返回其索引 2。
     * \
     * 输入：nums = [1,2,1,3,5,6,4]
     * 输出：1 或 5
     * 解释：你的函数可以返回索引 1，其峰值元素为 2；
     *      或者返回索引 5， 其峰值元素为 6。
     *  \
     * @param args args
     */
    public static void main(String[] args) {
        FindPeakElement findPeakElement = new FindPeakElement();
        int[] nums = new int[]{1,2,3,1};
        System.out.println(findPeakElement.findPeakElement(nums));
    }


    /**
     * 查找峰元素:循环遍历，找到一个元素比前一位大即可
     *
     * @param nums nums
     * @return int
     */
    public int findPeakElement(int[] nums) {
        int ans = 0;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i] > nums[i - 1]){
                ans = i;
            }
        }
        return ans;
    }

    /**
     * 查找峰元素2:二分查找
     * 对于当前可行的下标范围 [l,r]，我们随机一个下标 i；
     * 如果下标 i 是峰值，我们返回 i 作为答案；
     * 如果 nums[i]<nums[i+1]，那么我们抛弃 [l,i] 的范围，在剩余 [i+1,r] 的范围内继续随机选取下标；
     * 如果 nums[i]>nums[i+1]，那么我们抛弃 [i,r] 的范围，在剩余 [l,i−1] 的范围内继续随机选取下标。
     *
     * @param nums nums
     * @return int
     */
    public int findPeakElement2(int[] nums) {
        int len = nums.length;
        int left = 0,right = len - 1, ans = -1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            //左和右都满足峰值的条件
            if (this.helper(nums, mid - 1, mid) < 0 && this.helper(nums, mid, mid + 1) > 0) {
                ans = mid;
                break;
            }
            if (this.helper(nums, mid, mid + 1) < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

    /**
     * 帮手类
     *
     * @param nums   nums
     * @param index1 index1
     * @param index2 index2
     * @return int
     */
    private int helper(int[] nums, int index1, int index2) {
        int[] nums1 = this.getNums(nums,index1);
        int[] nums2= this.getNums(nums,index2);
        //其中一个值是边界值
        if(nums1[0] != nums2[0]){
            //按照峰值返回，如果1 则按照峰值说明曲线是从左到右叠加，-1是由左到右下降
            return nums1[1] > nums[0] ? 1 : -1;
        }
        //此情况说明没有峰值
        if(nums1[1] == nums2[1]){
            return 0;
        }
        return nums1[1] > nums[1] ? 1 : -1;
    }

    /**
     * 获取比较数组：方便处理 nums[-1] 以及 nums[n] 的边界情况
     * @param nums  nums
     * @param index 索引
     * @return {@link int[]}
     */
    private int[] getNums(int[] nums, int index) {
        //处理边界值
        if (index == -1 || index == nums.length) {
            return new int[]{0, 0};
        }
        //当前结点的值赋值到nums[1]
        return new int[]{1, nums[index]};
    }


}
